/**
 * Version 3.
 * Stream   = List<A>
 * Reason   = Error
 * Result   = Pair<Pair<List<C>, List<A>>?, Error?>
 *     1 or 0
 */
// some stubs
/*
fun <T> T?.add(x: T?): T? {
    return this
}

fun <T> T.comment(x: Any): T {
    return this
}

fun join<T>(x: T?, y: T?): T? {
    if (x == null)
        return y
    return x.add(y)
}

*/

// todo: refactor

package parcomb
import java.util.ArrayList

class Error() {
    //var info: Any? = null
}

// useful functions

fun isFailed<A, B> (r: Pair<Pair<List<B>, List<A>>?, Error?>) = r.first == null
fun isParsed<A, B> (r: Pair<Pair<List<B>, List<A>>?, Error?>) = r.first != null
fun getResult<A, B>(r: Pair<Pair<List<B>, List<A>>?, Error?>) = r.first!!.first
fun getStream<A, B>(r: Pair<Pair<List<B>, List<A>>?, Error?>) = r.first!!.second
fun getError<A, B> (r: Pair<Pair<List<B>, List<A>>?, Error?>) = r.second

fun result3<A, B>(r: List<B>, s: List<A>, e: Error? = null): Pair<Pair<List<B>, List<A>>?, Error?> = Pair(Pair(r, s), e)
fun single3<A, B>(r: B, s: List<A>, e: Error? = null): Pair<Pair<List<B>, List<A>>?, Error?> = Pair(Pair(asList(r), s), e)
fun empty<A, B>(s: List<A>, e: Error?): Pair<Pair<List<B>, List<A>>?, Error?> = Pair(Pair(asList<B>(), s), e)
fun failed<A, B>(e: Error?): Pair<Pair<List<B>, List<A>>?, Error?> = Pair(null, e)

// basic parsers

fun result<A, B>(r: B): (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?> =
        {(s: List<A>) -> single3<A, B>(r, s) }

fun zero<A, B>() = {(s: List<A>) -> result3<A, B>(asList(), s) }
fun fail<A, B>() = {(s: List<A>) -> failed<A, B>(null) }
fun list<A>() = {(s: List<A>) -> single3(s, s) }
fun item<A>() = {(s: List<A>) -> if (s.isEmpty()) failed<A, A>(null) else single3<A, A>(s[0], s.toEnd(1)) }
fun itemnc<A>() = {(s: List<A>) -> if (s.isEmpty()) failed<A, A>(null) else single3<A, A>(s[0], s) }

// some combinators

// bind combinator
fun bind<A, B, C>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        f: (B) -> ((List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?>)): (List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?> = {(s: List<A>) ->
    val ans = p(s)
    if (isFailed(ans))
        failed<A, C>(getError(ans))
    else {
        val r = getResult(ans)
        if (r.isEmpty())
            empty(getStream(ans), getError(ans))
        else
            f(r[0])(getStream(ans))
    }
}

fun bind1<A, B, C>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        f: (B?) -> ((List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?>)): (List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?> = {(s: List<A>) ->
    val ans = p(s)
    if (isFailed(ans))
        f(null)(s)
    else {
        val r = getResult(ans)
        if (r.isEmpty())
            f(null)(getStream(ans))
        else
            f(r[0])(getStream(ans))
    }
}

// sequence of parsers
fun seq<A, B, C>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        q: (List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<Pair<B, C>>, List<A>>?, Error?> =
        bind(p, {(x: B) ->
        bind(q, {(y: C) ->
            result(Pair(x, y))
        })})


// alternate choice
fun alt<A, B>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        q: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?> =
        {(s: List<A>) ->
            val ans = p(s)
            if (isParsed(ans))
                ans
            else
                q(s)
        }

// alternate more than 2 parsers
fun altl<A, B>(
        ps: List<(List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>>): (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?> =
        {(s: List<A>) ->
            if (ps.size == 0)
                failed(null)
            else {
                var ans = ps[0](s)
                if (isParsed(ans))
                    ans
                else
                    altl(ps.toEnd(1))(s)
            }
        }


// apply function to result
fun apply<A, B, C>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        f: (B) -> C): (List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?> = {(s: List<A>) ->
    val ans = p(s)
    if (ans.first == null)
        failed<A, C>(ans.second)
    else {
        val res = ans.first!!
        if (res.first.isEmpty())
            empty<A, C>(res.second, ans.second)
        else
            single3<A, C>(f(res.first[0]), res.second, ans.second)
    }
}

fun maybe<A, B>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>) = {(s: List<A>) ->
    val ans = p(s);
    if (isFailed(ans))
        empty<A, B>(s, null)
    else
        ans
}


// apply combinator more than once. Eager strategy
fun many<A, B>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<List<B>>, List<A>>?, Error?> =
        alt(
            bind(p, {(x: B) ->
            bind(many(p), {(xs: List<B>) ->
                result<A, List<B>>(x cons xs)
            })}),
            result(ArrayList<B>())
        )

// same as many, but combinator applies at least once
fun many1<A, B>(p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<List<B>>, List<A>>?, Error?> =
        bind(p, {(x: B) ->
        bind(many(p),{(xs: List<B>) ->
            result<A, List<B>>(x cons xs)
        })})


// surround combinator with 2 another, result of which you wont need
fun bracket<A, B, C, D>(
        open: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        p: (List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?>,
        close: (List<A>) -> Pair<Pair<List<D>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<C>, List<A>>?, Error?> =
        bind(open, {
        bind(p, {(ans: C) ->
        bind(close, {
            result<A, C>(ans)
        })})})

fun chainl1<A, B>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        op: (List<A>) -> Pair<Pair<List<(B, B) -> B>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?> = {(s: List<A>) ->
    val op2f = seq(op, p)
    val fys = many(op2f)
    bind<A, B, B>(
            p,
            {(x: B) ->
                bind<A, List<Pair<(B, B) -> B, B>>, B>(
                        fys,
                        {(xs: List<Pair<(B, B) -> B, B>>) ->
                            result(xs.foldl(
                                    {(x1: B, x2: Pair<(B, B) -> B, B>) -> x2.first(x1, x2.second) },
                                    x
                            ))
                        }
                )
            }
    )(s)
}

fun chainr1<A, B>(
        p: (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?>,
        op: (List<A>) -> Pair<Pair<List<(B, B) -> B>, List<A>>?, Error?>): (List<A>) -> Pair<Pair<List<B>, List<A>>?, Error?> = {(s: List<A>) ->
    val op2f = seq(op, p)
    val fys = many(op2f)
    bind<A, B, B>(
            p,
            {(x: B) ->
                bind<A, List<Pair<(B, B) -> B, B>>, B>(
                        fys,
                        {(xs: List<Pair<(B, B) -> B, B>>) ->
                            result(xs.foldr(
                                    {(x2: Pair<(B, B) -> B, B>, x1: B) -> x2.first(x1, x2.second) },
                                    x
                            ))
                        }
                )
            }
    )(s)
}

// useful parsers

// consume if symbol satisfies the predicate
fun sat<A>(f: (A) -> Boolean): (List<A>) -> Pair<Pair<List<A>, List<A>>?, Error?> =
        bind<A, A, A>(item<A>(), {(x: A) -> if (f(x)) result<A, A>(x) else fail() })

// consume if symbol is equal
fun char<A>(c: A) = sat<A>() { it == c }

// consume exact string
fun string<A>(str: List<A>): (List<A>) -> Pair<Pair<List<List<A>>, List<A>>?, Error?> =
        if (str.isEmpty())
            result<A, List<A>>(ArrayList<A>())
        else
            bind<A, A, List<A>>(
                    char(str[0]),
                    {(s0: A) ->
                        bind<A, List<A>, List<A>>(
                                string(str.subList(1, str.size())),
                                {(s1: List<A>) ->
                                    result<A, List<A>>(str)
                                }
                        )
                    }
            )

// string parsers (List<Char>)

fun digit() = sat<Char>() { it in '0'..'9' }
fun lower() = sat<Char>() { it in 'a'..'z' }
fun upper() = sat<Char>() { it in 'A'..'Z' }
fun letter() = alt(lower(), upper())
fun alphanum() = alt(letter(), digit())

fun digitToInt(): (List<Char>) -> Pair<Pair<List<Int>, List<Char>>?, Error?> =
        bind<Char, Char, Int>(
                digit(),
                {(x: Char) ->
                    result<Char, Int>(x.toInt() - '0'.toInt())
                }
        )



fun nat(): (List<Char>) -> Pair<Pair<List<Int>, List<Char>>?, Error?> = {(s: List<Char>) ->
    val ans = many1(digitToInt())(s)
    if (isFailed(ans))
        failed(ans.second)
    else {
        val res = ans.first!!
        if (res.first.isEmpty())
            empty(res.second, ans.second)
        else
            single3(res.first[0].foldl({(x: Int, y: Int) -> x * 10 + y }, 0), res.second, ans.second)
    }
}

fun int(): (List<Char>) -> Pair<Pair<List<Int>, List<Char>>?, Error?> = alt(
        bind<Char, Char, Int>(
                char('-'),
                {(x: Char) ->
                    bind<Char, Int, Int>(
                            nat(),
                            {(n: Int) -> result<Char, Int>(-n) }
                    )
                }
        ),
        nat()
)

//todo: rename old functions
/*
// TEST expression parser

fun getOp(op: Char) =
        when (op) {
            '+' -> {(x: Int, y: Int) -> x + y }
            '-' -> {(x: Int, y: Int) -> x - y }
            '*' -> {(x: Int, y: Int) -> x * y }
            else -> {(x: Int, y: Int) -> 0 }
        }

fun addop(): (List<Char>) -> Pair<Pair<List<((Int, Int) -> Int)>, List<Char>>?, Error?> = alt(
        apply<Char, Char, (Int, Int) -> Int>(char<Char>('+'), {(c: Char) -> getOp(c) }),
        apply<Char, Char, (Int, Int) -> Int>(char<Char>('-'), {(c: Char) -> getOp(c) })
)

fun multop(): (List<Char>) -> Pair<Pair<List<((Int, Int) -> Int)>, List<Char>>?, Error?> =
        apply<Char, Char, (Int, Int) -> Int>(char<Char>('*'), {(c: Char) -> getOp(c) })

fun expr() = chainl1<Char, Int>(term(), addop())
fun term() = chainl1<Char, Int>(factor(), multop())
fun factor(): (List<Char>) -> Pair<Pair<List<Int>, List<Char>>?, Error?> = alt(
        nat(),
        bracket(char('('), {(s) -> expr()(s) }, char(')'))
)              */